package org.huawei260.basic.part_3_tree.BST;

/**
 * @Author: qingle
 * @Date: 2024/11/29-13:53
 * @Description:
 * 将进一步探索一个特殊的二叉树——二叉搜索树。它将数据的有序性和树的层级结构完美地结合在了一起，使得查找、插入和删除等操作更加高效。
 *
 * 特性：有序性
 * 对于任一节点 N，其左子树中所有节点的值都小于节点 N 的值，而右子树中所有节点的值都大于节点 N 的值。
 *
 * 二叉搜索树的优势在于其插入和删除操作的时间复杂度都是 O(log n)，而二叉树的插入和删除操作的时间复杂度都是 O(n)。
 *
 * // 插入：从根节点开始插入，找到合适的位置，然后插入新节点。如果当前插入的值小于当前节点的值，则继续在左子树中寻找合适的位置；如果当前插入的值大于当前节点的值，则继续在右子树中寻找合适的位置。
 * // 删除：从根节点开始删除，找到要删除的节点，然后根据节点的子节点数量进行删除操作。如果要删除的节点没有子节点，则直接删除该节点；如果要删除的节点有一个子节点，则将子节点替换为要删除的节点；如果要删除
 * 的节点有两个子节点，则需要找到要删除节点的后继节点（即右子树中的最小节点），将后继节点的值替换为要删除节点的值，然后删除后继节点。
 * // 查找：类似于插入，从根节点开始查找，找到要查找的节点，然后返回该节点。如果要查找的节点不存在，则返回 null。
 *
 *
 * 二叉搜索树的主要应用场景包括：
 * 1. 数据库索引：在数据库中，索引通常是基于二叉搜索树的。
 * 2. 排序算法：二叉搜索树可以用于实现各种排序算法，如快速排序、归并排序等。
 * 3. 符号表：二叉搜索树可以用于实现各种符号表，如红黑树、AVL树等。
 *
 * @Version: 1.0
 */
public class BinarySearchTree {

	static class Node {
		int value;
		Node left;
		Node right;

		public Node(int value) {
			this.value = value;
		}

	}

	static class BST {
		Node root;

		void insert(int value) {
			root = insert(root, value);
			System.out.println("插入的数据：" + root.value);
		}

		private Node insert(Node root, int value) {
			if(root == null) {
				return new Node(value);
			}
			if(value < root.value) {
				// 在左侧插入
				root.left = insert(root.left, value);
			} else {
				root.right = insert(root.right, value);
			}
			return root;
		}

		// 查找
		Node search(Node node, int value) {
			if(node == null) return null;
			if(node.value == value) {
				return node;
			}
			if(value < node.value) {
				search(node.left, value);
			} else {
				search(node.right, value);
			}
			return null;
		}

		// 打印二叉树的方法
		void printTree() {
			printTreeRecursive(root, 0);
		}

		private void printTreeRecursive(Node node, int level) {
			if (node == null) return;
//			System.out.println("level: " + level + ", value: " + node.value);
			// 先打印右子树
			printTreeRecursive(node.right, level + 1);
			// 打印当前节点
			for (int i = 0; i < level; i++) {
				System.out.println(" ");
			}
			System.out.println(node.value);
			// 再打印左子树
			printTreeRecursive(node.left, level + 1);
		}

//		Node delete(Node node, int value) {
//			if(node == null) return null;
//			if(value == node.value) {
//
//			}
//			if(value < node.value) {
//				delete(node.left, value);
//			}else{
//
//			}
//		}

		// 删除节点实现
		Node delete(Node node, int value) {
			if(node == null) return null;
			if(value < node.value) {
				node.left = delete(node.left, value);
			} else if(value > node.value) {
				node.right = delete(node.right, value);
			} else {
				// 待删除节点有两个子节点
				if(node.left != null && node.right != null) {
					// 找到后继节点，即右子树中最小的节点
					Node successor = node.right;
					while(successor.left != null) {
						successor = successor.left;
						successor.left = delete(successor.left, successor.value);
						successor.right = delete(successor.right, successor.value);
						return successor;
					}
				}
			}
			return node;
		}
	}

	public static void main(String[] args) {
		BST tree = new BST();
		tree.insert(5);
		tree.insert(6);
		tree.insert(7);
		tree.insert(8);
		tree.insert(9);
		tree.insert(10);
		tree.insert(11);
		tree.insert(4);
		tree.printTree();
	}

}
